package com.lwl.Algorithmic_data_structure.class25单调栈;

import com.lwl.Utils.PrintUtil;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 单调栈，给你一个数组，请你求出每个元素距离最近比他小的元素的位置
 * arr = [ 3, 1, 2, 4]
 * 0  1  2  3
 * [
 * 0 : [-1,  1]
 * 1 : [-1, -1]
 * 2 : [ 1, -1]
 * 3 : [ 2, -1]
 * ]
 * @date 2023/6/25 20:47
 */
public class Code01MonotonousStackNoRepeat {

    public static void main(String[] args) {
//        int[][] array = monotonousStack(new int[]{3, 1, 2, 4});
        int[][] array = monotonousStack(new int[]{4, 2, 5, 3, 1, 0});
        PrintUtil.printArray(array);
    }

    public static int[][] monotonousStack(int[] array) {
        LinkedList<Integer> stack = new LinkedList<>();
        int[][] res = new int[array.length][2];
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast()] > array[i]) {
                Integer pollLast = stack.pollLast();
                res[pollLast][0] = stack.isEmpty() ? -1 : stack.peekLast();
                res[pollLast][1] = i;
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            Integer pollLast = stack.pollLast();
            res[pollLast][1] = -1;
            res[pollLast][0] = stack.isEmpty() ? -1 : stack.peekLast();
        }
        return res;
    }

}
